package reverseList;

public class Solution {
      public class ListNode {
      int val;
      ListNode next;
      ListNode() {}
      ListNode(int val) { this.val = val; }
      ListNode(int val, ListNode next) { this.val = val; this.next = next; }
  }
    public ListNode reverseList(ListNode head) {
        // 栈
//        Stack<ListNode> stack = new Stack<>();
//        ListNode p = head;
//        while (p!=null) {
//            stack.add(p);
//            p = p.next;
//        }
//        ListNode ans = new ListNode();
//        p = ans;
//        while (!stack.isEmpty()) {
//            p.next = stack.pop();
//            p = p.next;
//        }
//        p.next = null;
//        return ans.next;
        // 双指针
//        ListNode p1 = head;
//        ListNode p2 = null;
//        // p1.next = p2
//        while (p1!=null) {
//            ListNode p = p1.next;
//            p1.next = p2;
//            p2 = p1;
//            p1 = p;
//        }
//        return p2;

        ListNode parent = head;
        ListNode child = null;
        while (parent!=null) {
            ListNode t = parent.next;
            parent.next = child;
            child = parent;
            parent = t;
        }
        return child;
    }
}
